package 字符串.重复的子字符串;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/1/17 16:56
 * @description:
 * @version:
 */
public class Solution {
    public static void main(String[] args) {

    }


    /**
     * 如果S不包含重复的子字符串，则S本身就是所谓的“重复子字符串”（这里方便自己理解，视为重复一次，不深究= =）
     * ，str = S+S,说明S是str的重复子字符串，刨去str首尾两个字符之后（相当于分别破坏前一个S头部和后一个S尾部），不能满足str包含S
     * @param s
     * @return
     */
    //官方解法，自己没有想出来!!!  牛逼
    public static boolean repeatedSubstringPattern(String s) {
        String str = s + s;
        return str.substring(1, str.length() - 1).contains(s);
    }

    //暴力代码
    public  static boolean repeatedSubstringPattern2(String s) {
        for(int i = 1; i < s.length(); i++) {
            String str = rotate(s.toCharArray(),i);
            if(s.equals(str)) return true;
        }
        return false;
    }


    public static String rotate(char[] nums, int k) {
        k = k % nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
        return String.valueOf(nums);
    }

    public static void reverse(char[] nums, int begin, int end) {
        int i = begin, j = end;
        while(i < j) {
            char temp = nums[i];
            nums[i++] = nums[j];
            nums[j--] = temp;
        }
    }


    //KMP算法，待学习
    public static boolean repeatedSubstringPattern3(String s) {
        if (s.equals("")) return false;

        int len = s.length();
        // 原串加个空格(哨兵)，使下标从1开始，这样j从0开始，也不用初始化了
        s = " " + s;
        char[] chars = s.toCharArray();
        int[] next = new int[len + 1];

        // 构造 next 数组过程，j从0开始(空格)，i从2开始
        for (int i = 2, j = 0; i <= len; i++) {
            // 匹配不成功，j回到前一位置 next 数组所对应的值
            while (j > 0 && chars[i] != chars[j + 1])
                j = next[j];
            // 匹配成功，j往后移
            if (chars[i] == chars[j + 1]) j++;
            // 更新 next 数组的值
            next[i] = j;
        }

        // 最后判断是否是重复的子字符串，这里 next[len] 即代表next数组末尾的值
        if (next[len] > 0 && len % (len - next[len]) == 0) {
            return true;
        }
        return false;
    }

}
